﻿{ License, info, etc
  ------------------

  This implementation is made by Walied Othman, to contact me
  mail to Walied.Othman@Student.KULeuven.ac.be or
  Triade@ace.Ulyssis.Student.KULeuven.ac.be,
  always mention wether it 's about the FGInt for Delphi or for
  FreePascal, or wether it 's about the 6xs, preferably in the subject line.
  If you 're going to use these implementations, at least mention my
  name or something and notify me so I may even put a link on my page.
  This implementation is freeware and according to the coderpunks'
  manifesto it should remain so, so don 't use these implementations
  in commercial software.  Encryption, as a tool to ensure privacy
  should be free and accessible for anyone.  If you plan to use these
  implementations in a commercial application, contact me before
  doing so, that way you can license the software to use it in commercial
  Software.  If any algorithm is patented in your country, you should
  acquire a license before using this software.  Modified versions of this
  software must contain an acknowledgement of the original author (=me).
  This implementaion is available at
  http://ace.ulyssis.student.kuleuven.ac.be/~triade/

  copyright 2000, Walied Othman
  This header may not be removed.
}

Unit FGInt;

Interface

Uses Windows, SysUtils, Controls, Math, StrUtils;

Type
  TCompare = (Lt, St, Eq, Er);
  TSign = (negative, positive);

  TFGInt = Record
    Sign: TSign;
    Number: Array Of int64;
  End;

Procedure zeronetochar8(Var g: AnsiChar; Const x: AnsiString);
Procedure zeronetochar6(Var g: integer; Const x: AnsiString);
Procedure initialize8(Var trans: Array Of AnsiString);
Procedure initialize6(Var trans: Array Of AnsiString);
Procedure initialize6PGP(Var trans: Array Of AnsiString);
Procedure ConvertBase256to64(Const str256: AnsiString; Var str64: AnsiString);
Procedure ConvertBase64to256(Const str64: AnsiString; Var str256: AnsiString);
Procedure ConvertBase256to2(Const str256: AnsiString; Var str2: AnsiString);
Procedure ConvertBase64to2(Const str64: AnsiString; Var str2: AnsiString);
Procedure ConvertBase2to256(str2: AnsiString; Var str256: AnsiString);
Procedure ConvertBase2to64(str2: AnsiString; Var str64: AnsiString);
Procedure ConvertBase256StringToHexString(str256: AnsiString;
  Var HexStr: AnsiString);
Procedure ConvertHexStringToBase256String(HexStr: AnsiString;
  Var str256: AnsiString);
Procedure PGPConvertBase256to64(Var str256, str64: AnsiString);
Procedure PGPConvertBase64to256(str64: AnsiString; Var str256: AnsiString);
Procedure PGPConvertBase64to2(str64: AnsiString; Var str2: AnsiString);
Procedure Base10StringToFGInt(Base10: AnsiString; Var FGInt: TFGInt);
Procedure FGIntToBase10String(Const FGInt: TFGInt; Var Base10: AnsiString);
Procedure FGIntDestroy(Var FGInt: TFGInt);
Function FGIntCompareAbs(Const FGInt1, FGInt2: TFGInt): TCompare;
Procedure FGIntAdd(Const FGInt1, FGInt2: TFGInt; Var Sum: TFGInt);
Procedure FGIntChangeSign(Var FGInt: TFGInt);
Procedure FGIntSub(Var FGInt1, FGInt2, dif: TFGInt);
Procedure FGIntMulByInt(Const FGInt: TFGInt; Var res: TFGInt; by: int64);
Procedure FGIntMulByIntbis(Var FGInt: TFGInt; by: int64);
Procedure FGIntDivByInt(Const FGInt: TFGInt; Var res: TFGInt; by: int64;
  Var modres: int64);
Procedure FGIntDivByIntBis(Var FGInt: TFGInt; by: int64; Var modres: int64);
Procedure FGIntModByInt(Const FGInt: TFGInt; by: int64; Var modres: int64);
Procedure FGIntAbs(Var FGInt: TFGInt);
Procedure FGIntCopy(Const FGInt1: TFGInt; Var FGInt2: TFGInt);
Procedure FGIntShiftLeft(Var FGInt: TFGInt);
Procedure FGIntShiftRight(Var FGInt: TFGInt);
Procedure FGIntShiftRightBy31(Var FGInt: TFGInt);
Procedure FGIntAddBis(Var FGInt1: TFGInt; Const FGInt2: TFGInt);
Procedure FGIntSubBis(Var FGInt1: TFGInt; Const FGInt2: TFGInt);
Procedure FGIntMul(Const FGInt1, FGInt2: TFGInt; Var Prod: TFGInt);
Procedure FGIntSquare(Const FGInt: TFGInt; Var Square: TFGInt);
Procedure FGIntToBase2String(Const FGInt: TFGInt; Var S: AnsiString);
Procedure Base2StringToFGInt(S: AnsiString; Var FGInt: TFGInt);
Procedure FGIntToBase256String(Const FGInt: TFGInt; Var str256: AnsiString);
Procedure Base256StringToFGInt(str256: AnsiString; Var FGInt: TFGInt);
Procedure PGPMPIToFGInt(PGPMPI: AnsiString; Var FGInt: TFGInt);
Procedure FGIntToPGPMPI(FGInt: TFGInt; Var PGPMPI: AnsiString);
Procedure FGIntExp(Const FGInt, exp: TFGInt; Var res: TFGInt);
Procedure FGIntFac(Const FGInt: TFGInt; Var res: TFGInt);
Procedure FGIntShiftLeftBy31(Var FGInt: TFGInt);
Procedure FGIntDivMod(Var FGInt1, FGInt2, QFGInt, MFGInt: TFGInt);
Procedure FGIntDiv(Var FGInt1, FGInt2, QFGInt: TFGInt);
Procedure FGIntMod(Var FGInt1, FGInt2, MFGInt: TFGInt);
Procedure FGIntSquareMod(Var FGInt, Modb, FGIntSM: TFGInt);
Procedure FGIntAddMod(Var FGInt1, FGInt2, base, FGIntres: TFGInt);
Procedure FGIntMulMod(Var FGInt1, FGInt2, base, FGIntres: TFGInt);
Procedure FGIntModExp(Var FGInt, exp, Modb, res: TFGInt);
Procedure FGIntModBis(Const FGInt: TFGInt; Var FGIntOut: TFGInt; b: longint;
  head: int64);
Procedure FGIntMulModBis(Const FGInt1, FGInt2: TFGInt; Var Prod: TFGInt;
  b: longint; head: int64);
Procedure FGIntMontgomeryMod(Const GInt, base, baseInv: TFGInt;
  Var MGInt: TFGInt; b: longint; head: int64);
Procedure FGIntMontgomeryModExp(Var FGInt, exp, Modb, res: TFGInt);
Procedure FGIntGCD(Const FGInt1, FGInt2: TFGInt; Var GCD: TFGInt);
Procedure FGIntLCM(Const FGInt1, FGInt2: TFGInt; Var LCM: TFGInt);
Procedure FGIntTrialDiv9999(Const FGInt: TFGInt; Var ok: boolean);
Procedure FGIntRandom1(Var Seed, RandomFGInt: TFGInt);
Procedure FGIntRabinMiller(Var FGIntp: TFGInt; nrtest: integer;
  Var ok: boolean);
Procedure FGIntBezoutBachet(Var FGInt1, FGInt2, a, b: TFGInt);
Procedure FGIntModInv(Const FGInt1, base: TFGInt; Var Inverse: TFGInt);
Procedure FGIntPrimetest(Var FGIntp: TFGInt; nrRMtests: integer;
  Var ok: boolean);
Procedure FGIntLegendreSymbol(Var a, p: TFGInt; Var L: integer);
Procedure FGIntSquareRootModP(Square, Prime: TFGInt; Var SquareRoot: TFGInt);

Implementation

Var
  primes: Array [1 .. 1228] Of integer = (
    3,
    5,
    7,
    11,
    13,
    17,
    19,
    23,
    29,
    31,
    37,
    41,
    43,
    47,
    53,
    59,
    61,
    67,
    71,
    73,
    79,
    83,
    89,
    97,
    101,
    103,
    107,
    109,
    113,
    127,
    131,
    137,
    139,
    149,
    151,
    157,
    163,
    167,
    173,
    179,
    181,
    191,
    193,
    197,
    199,
    211,
    223,
    227,
    229,
    233,
    239,
    241,
    251,
    257,
    263,
    269,
    271,
    277,
    281,
    283,
    293,
    307,
    311,
    313,
    317,
    331,
    337,
    347,
    349,
    353,
    359,
    367,
    373,
    379,
    383,
    389,
    397,
    401,
    409,
    419,
    421,
    431,
    433,
    439,
    443,
    449,
    457,
    461,
    463,
    467,
    479,
    487,
    491,
    499,
    503,
    509,
    521,
    523,
    541,
    547,
    557,
    563,
    569,
    571,
    577,
    587,
    593,
    599,
    601,
    607,
    613,
    617,
    619,
    631,
    641,
    643,
    647,
    653,
    659,
    661,
    673,
    677,
    683,
    691,
    701,
    709,
    719,
    727,
    733,
    739,
    743,
    751,
    757,
    761,
    769,
    773,
    787,
    797,
    809,
    811,
    821,
    823,
    827,
    829,
    839,
    853,
    857,
    859,
    863,
    877,
    881,
    883,
    887,
    907,
    911,
    919,
    929,
    937,
    941,
    947,
    953,
    967,
    971,
    977,
    983,
    991,
    997,
    1009,
    1013,
    1019,
    1021,
    1031,
    1033,
    1039,
    1049,
    1051,
    1061,
    1063,
    1069,
    1087,
    1091,
    1093,
    1097,
    1103,
    1109,
    1117,
    1123,
    1129,
    1151,
    1153,
    1163,
    1171,
    1181,
    1187,
    1193,
    1201,
    1213,
    1217,
    1223,
    1229,
    1231,
    1237,
    1249,
    1259,
    1277,
    1279,
    1283,
    1289,
    1291,
    1297,
    1301,
    1303,
    1307,
    1319,
    1321,
    1327,
    1361,
    1367,
    1373,
    1381,
    1399,
    1409,
    1423,
    1427,
    1429,
    1433,
    1439,
    1447,
    1451,
    1453,
    1459,
    1471,
    1481,
    1483,
    1487,
    1489,
    1493,
    1499,
    1511,
    1523,
    1531,
    1543,
    1549,
    1553,
    1559,
    1567,
    1571,
    1579,
    1583,
    1597,
    1601,
    1607,
    1609,
    1613,
    1619,
    1621,
    1627,
    1637,
    1657,
    1663,
    1667,
    1669,
    1693,
    1697,
    1699,
    1709,
    1721,
    1723,
    1733,
    1741,
    1747,
    1753,
    1759,
    1777,
    1783,
    1787,
    1789,
    1801,
    1811,
    1823,
    1831,
    1847,
    1861,
    1867,
    1871,
    1873,
    1877,
    1879,
    1889,
    1901,
    1907,
    1913,
    1931,
    1933,
    1949,
    1951,
    1973,
    1979,
    1987,
    1993,
    1997,
    1999,
    2003,
    2011,
    2017,
    2027,
    2029,
    2039,
    2053,
    2063,
    2069,
    2081,
    2083,
    2087,
    2089,
    2099,
    2111,
    2113,
    2129,
    2131,
    2137,
    2141,
    2143,
    2153,
    2161,
    2179,
    2203,
    2207,
    2213,
    2221,
    2237,
    2239,
    2243,
    2251,
    2267,
    2269,
    2273,
    2281,
    2287,
    2293,
    2297,
    2309,
    2311,
    2333,
    2339,
    2341,
    2347,
    2351,
    2357,
    2371,
    2377,
    2381,
    2383,
    2389,
    2393,
    2399,
    2411,
    2417,
    2423,
    2437,
    2441,
    2447,
    2459,
    2467,
    2473,
    2477,
    2503,
    2521,
    2531,
    2539,
    2543,
    2549,
    2551,
    2557,
    2579,
    2591,
    2593,
    2609,
    2617,
    2621,
    2633,
    2647,
    2657,
    2659,
    2663,
    2671,
    2677,
    2683,
    2687,
    2689,
    2693,
    2699,
    2707,
    2711,
    2713,
    2719,
    2729,
    2731,
    2741,
    2749,
    2753,
    2767,
    2777,
    2789,
    2791,
    2797,
    2801,
    2803,
    2819,
    2833,
    2837,
    2843,
    2851,
    2857,
    2861,
    2879,
    2887,
    2897,
    2903,
    2909,
    2917,
    2927,
    2939,
    2953,
    2957,
    2963,
    2969,
    2971,
    2999,
    3001,
    3011,
    3019,
    3023,
    3037,
    3041,
    3049,
    3061,
    3067,
    3079,
    3083,
    3089,
    3109,
    3119,
    3121,
    3137,
    3163,
    3167,
    3169,
    3181,
    3187,
    3191,
    3203,
    3209,
    3217,
    3221,
    3229,
    3251,
    3253,
    3257,
    3259,
    3271,
    3299,
    3301,
    3307,
    3313,
    3319,
    3323,
    3329,
    3331,
    3343,
    3347,
    3359,
    3361,
    3371,
    3373,
    3389,
    3391,
    3407,
    3413,
    3433,
    3449,
    3457,
    3461,
    3463,
    3467,
    3469,
    3491,
    3499,
    3511,
    3517,
    3527,
    3529,
    3533,
    3539,
    3541,
    3547,
    3557,
    3559,
    3571,
    3581,
    3583,
    3593,
    3607,
    3613,
    3617,
    3623,
    3631,
    3637,
    3643,
    3659,
    3671,
    3673,
    3677,
    3691,
    3697,
    3701,
    3709,
    3719,
    3727,
    3733,
    3739,
    3761,
    3767,
    3769,
    3779,
    3793,
    3797,
    3803,
    3821,
    3823,
    3833,
    3847,
    3851,
    3853,
    3863,
    3877,
    3881,
    3889,
    3907,
    3911,
    3917,
    3919,
    3923,
    3929,
    3931,
    3943,
    3947,
    3967,
    3989,
    4001,
    4003,
    4007,
    4013,
    4019,
    4021,
    4027,
    4049,
    4051,
    4057,
    4073,
    4079,
    4091,
    4093,
    4099,
    4111,
    4127,
    4129,
    4133,
    4139,
    4153,
    4157,
    4159,
    4177,
    4201,
    4211,
    4217,
    4219,
    4229,
    4231,
    4241,
    4243,
    4253,
    4259,
    4261,
    4271,
    4273,
    4283,
    4289,
    4297,
    4327,
    4337,
    4339,
    4349,
    4357,
    4363,
    4373,
    4391,
    4397,
    4409,
    4421,
    4423,
    4441,
    4447,
    4451,
    4457,
    4463,
    4481,
    4483,
    4493,
    4507,
    4513,
    4517,
    4519,
    4523,
    4547,
    4549,
    4561,
    4567,
    4583,
    4591,
    4597,
    4603,
    4621,
    4637,
    4639,
    4643,
    4649,
    4651,
    4657,
    4663,
    4673,
    4679,
    4691,
    4703,
    4721,
    4723,
    4729,
    4733,
    4751,
    4759,
    4783,
    4787,
    4789,
    4793,
    4799,
    4801,
    4813,
    4817,
    4831,
    4861,
    4871,
    4877,
    4889,
    4903,
    4909,
    4919,
    4931,
    4933,
    4937,
    4943,
    4951,
    4957,
    4967,
    4969,
    4973,
    4987,
    4993,
    4999,
    5003,
    5009,
    5011,
    5021,
    5023,
    5039,
    5051,
    5059,
    5077,
    5081,
    5087,
    5099,
    5101,
    5107,
    5113,
    5119,
    5147,
    5153,
    5167,
    5171,
    5179,
    5189,
    5197,
    5209,
    5227,
    5231,
    5233,
    5237,
    5261,
    5273,
    5279,
    5281,
    5297,
    5303,
    5309,
    5323,
    5333,
    5347,
    5351,
    5381,
    5387,
    5393,
    5399,
    5407,
    5413,
    5417,
    5419,
    5431,
    5437,
    5441,
    5443,
    5449,
    5471,
    5477,
    5479,
    5483,
    5501,
    5503,
    5507,
    5519,
    5521,
    5527,
    5531,
    5557,
    5563,
    5569,
    5573,
    5581,
    5591,
    5623,
    5639,
    5641,
    5647,
    5651,
    5653,
    5657,
    5659,
    5669,
    5683,
    5689,
    5693,
    5701,
    5711,
    5717,
    5737,
    5741,
    5743,
    5749,
    5779,
    5783,
    5791,
    5801,
    5807,
    5813,
    5821,
    5827,
    5839,
    5843,
    5849,
    5851,
    5857,
    5861,
    5867,
    5869,
    5879,
    5881,
    5897,
    5903,
    5923,
    5927,
    5939,
    5953,
    5981,
    5987,
    6007,
    6011,
    6029,
    6037,
    6043,
    6047,
    6053,
    6067,
    6073,
    6079,
    6089,
    6091,
    6101,
    6113,
    6121,
    6131,
    6133,
    6143,
    6151,
    6163,
    6173,
    6197,
    6199,
    6203,
    6211,
    6217,
    6221,
    6229,
    6247,
    6257,
    6263,
    6269,
    6271,
    6277,
    6287,
    6299,
    6301,
    6311,
    6317,
    6323,
    6329,
    6337,
    6343,
    6353,
    6359,
    6361,
    6367,
    6373,
    6379,
    6389,
    6397,
    6421,
    6427,
    6449,
    6451,
    6469,
    6473,
    6481,
    6491,
    6521,
    6529,
    6547,
    6551,
    6553,
    6563,
    6569,
    6571,
    6577,
    6581,
    6599,
    6607,
    6619,
    6637,
    6653,
    6659,
    6661,
    6673,
    6679,
    6689,
    6691,
    6701,
    6703,
    6709,
    6719,
    6733,
    6737,
    6761,
    6763,
    6779,
    6781,
    6791,
    6793,
    6803,
    6823,
    6827,
    6829,
    6833,
    6841,
    6857,
    6863,
    6869,
    6871,
    6883,
    6899,
    6907,
    6911,
    6917,
    6947,
    6949,
    6959,
    6961,
    6967,
    6971,
    6977,
    6983,
    6991,
    6997,
    7001,
    7013,
    7019,
    7027,
    7039,
    7043,
    7057,
    7069,
    7079,
    7103,
    7109,
    7121,
    7127,
    7129,
    7151,
    7159,
    7177,
    7187,
    7193,
    7207,
    7211,
    7213,
    7219,
    7229,
    7237,
    7243,
    7247,
    7253,
    7283,
    7297,
    7307,
    7309,
    7321,
    7331,
    7333,
    7349,
    7351,
    7369,
    7393,
    7411,
    7417,
    7433,
    7451,
    7457,
    7459,
    7477,
    7481,
    7487,
    7489,
    7499,
    7507,
    7517,
    7523,
    7529,
    7537,
    7541,
    7547,
    7549,
    7559,
    7561,
    7573,
    7577,
    7583,
    7589,
    7591,
    7603,
    7607,
    7621,
    7639,
    7643,
    7649,
    7669,
    7673,
    7681,
    7687,
    7691,
    7699,
    7703,
    7717,
    7723,
    7727,
    7741,
    7753,
    7757,
    7759,
    7789,
    7793,
    7817,
    7823,
    7829,
    7841,
    7853,
    7867,
    7873,
    7877,
    7879,
    7883,
    7901,
    7907,
    7919,
    7927,
    7933,
    7937,
    7949,
    7951,
    7963,
    7993,
    8009,
    8011,
    8017,
    8039,
    8053,
    8059,
    8069,
    8081,
    8087,
    8089,
    8093,
    8101,
    8111,
    8117,
    8123,
    8147,
    8161,
    8167,
    8171,
    8179,
    8191,
    8209,
    8219,
    8221,
    8231,
    8233,
    8237,
    8243,
    8263,
    8269,
    8273,
    8287,
    8291,
    8293,
    8297,
    8311,
    8317,
    8329,
    8353,
    8363,
    8369,
    8377,
    8387,
    8389,
    8419,
    8423,
    8429,
    8431,
    8443,
    8447,
    8461,
    8467,
    8501,
    8513,
    8521,
    8527,
    8537,
    8539,
    8543,
    8563,
    8573,
    8581,
    8597,
    8599,
    8609,
    8623,
    8627,
    8629,
    8641,
    8647,
    8663,
    8669,
    8677,
    8681,
    8689,
    8693,
    8699,
    8707,
    8713,
    8719,
    8731,
    8737,
    8741,
    8747,
    8753,
    8761,
    8779,
    8783,
    8803,
    8807,
    8819,
    8821,
    8831,
    8837,
    8839,
    8849,
    8861,
    8863,
    8867,
    8887,
    8893,
    8923,
    8929,
    8933,
    8941,
    8951,
    8963,
    8969,
    8971,
    8999,
    9001,
    9007,
    9011,
    9013,
    9029,
    9041,
    9043,
    9049,
    9059,
    9067,
    9091,
    9103,
    9109,
    9127,
    9133,
    9137,
    9151,
    9157,
    9161,
    9173,
    9181,
    9187,
    9199,
    9203,
    9209,
    9221,
    9227,
    9239,
    9241,
    9257,
    9277,
    9281,
    9283,
    9293,
    9311,
    9319,
    9323,
    9337,
    9341,
    9343,
    9349,
    9371,
    9377,
    9391,
    9397,
    9403,
    9413,
    9419,
    9421,
    9431,
    9433,
    9437,
    9439,
    9461,
    9463,
    9467,
    9473,
    9479,
    9491,
    9497,
    9511,
    9521,
    9533,
    9539,
    9547,
    9551,
    9587,
    9601,
    9613,
    9619,
    9623,
    9629,
    9631,
    9643,
    9649,
    9661,
    9677,
    9679,
    9689,
    9697,
    9719,
    9721,
    9733,
    9739,
    9743,
    9749,
    9767,
    9769,
    9781,
    9787,
    9791,
    9803,
    9811,
    9817,
    9829,
    9833,
    9839,
    9851,
    9857,
    9859,
    9871,
    9883,
    9887,
    9901,
    9907,
    9923,
    9929,
    9931,
    9941,
    9949,
    9967,
    9973
  );
  chr64: Array [1 .. 64] Of AnsiChar = (
    'a',
    'A',
    'b',
    'B',
    'c',
    'C',
    'd',
    'D',
    'e',
    'E',
    'f',
    'F',
    'g',
    'G',
    'h',
    'H',
    'i',
    'I',
    'j',
    'J',
    'k',
    'K',
    'l',
    'L',
    'm',
    'M',
    'n',
    'N',
    'o',
    'O',
    'p',
    'P',
    'q',
    'Q',
    'r',
    'R',
    's',
    'S',
    't',
    'T',
    'u',
    'U',
    'v',
    'V',
    'w',
    'W',
    'x',
    'X',
    'y',
    'Y',
    'z',
    'Z',
    '0',
    '1',
    '2',
    '3',
    '4',
    '5',
    '6',
    '7',
    '8',
    '9',
    '+',
    '='
  );
  PGPchr64: Array [1 .. 64] Of AnsiChar = (
    'A',
    'B',
    'C',
    'D',
    'E',
    'F',
    'G',
    'H',
    'I',
    'J',
    'K',
    'L',
    'M',
    'N',
    'O',
    'P',
    'Q',
    'R',
    'S',
    'T',
    'U',
    'V',
    'W',
    'X',
    'Y',
    'Z',
    'a',
    'b',
    'c',
    'd',
    'e',
    'f',
    'g',
    'h',
    'i',
    'j',
    'k',
    'l',
    'm',
    'n',
    'o',
    'p',
    'q',
    'r',
    's',
    't',
    'u',
    'v',
    'w',
    'x',
    'y',
    'z',
    '0',
    '1',
    '2',
    '3',
    '4',
    '5',
    '6',
    '7',
    '8',
    '9',
    '+',
    '/'
  );

{$H+}

Procedure zeronetochar8(Var g: AnsiChar; Const x: AnsiString);
Var
  i: integer;
  b: byte;
Begin
  b := 0;
  For i := 1 To 8 Do
  Begin
    If copy(x, i, 1) = '1' Then
      b := b Or (1 Shl (8 - i));
  End;
  g := AnsiChar(b);
End;

Procedure zeronetochar6(Var g: integer; Const x: AnsiString);
Var
  i: integer;
Begin
  g := 0;
  For i := 1 To Length(x) Do
  Begin
    If i > 6 Then
      Break;
    If x[i] <> '0' Then
      g := g Or (1 Shl (6 - i));
  End;
  Inc(g);
End;

Procedure initialize8(Var trans: Array Of AnsiString);
Var
  c1, c2, c3, c4, c5, c6, c7, c8: integer;
  x: AnsiString;
  g: AnsiChar;
Begin
  For c1 := 0 To 1 Do
    For c2 := 0 To 1 Do
      For c3 := 0 To 1 Do
        For c4 := 0 To 1 Do
          For c5 := 0 To 1 Do
            For c6 := 0 To 1 Do
              For c7 := 0 To 1 Do
                For c8 := 0 To 1 Do
                Begin
                  x := '';
                  x := AnsiString(inttostr(c1) + inttostr(c2) + inttostr(c3) +
                    inttostr(c4) + inttostr(c5) + inttostr(c6) + inttostr(c7) +
                    inttostr(c8));
                  zeronetochar8(g, x);
                  trans[ord(g)] := x;
                End;
End;

Procedure initialize6(Var trans: Array Of AnsiString);
Var
  c1, c2, c3, c4, c5, c6: integer;
  x: AnsiString;
  g: integer;
Begin
  For c1 := 0 To 1 Do
    For c2 := 0 To 1 Do
      For c3 := 0 To 1 Do
        For c4 := 0 To 1 Do
          For c5 := 0 To 1 Do
            For c6 := 0 To 1 Do
            Begin
              x := '';
              x := AnsiString(inttostr(c1) + inttostr(c2) + inttostr(c3) +
                inttostr(c4) + inttostr(c5) + inttostr(c6));
              zeronetochar6(g, x);
              trans[ord(chr64[g])] := x;
            End;
End;

Procedure initialize6PGP(Var trans: Array Of AnsiString);
Var
  c1, c2, c3, c4, c5, c6: integer;
  x: AnsiString;
  g: integer;
Begin
  For c1 := 0 To 1 Do
    For c2 := 0 To 1 Do
      For c3 := 0 To 1 Do
        For c4 := 0 To 1 Do
          For c5 := 0 To 1 Do
            For c6 := 0 To 1 Do
            Begin
              x := '';
              x := AnsiString(inttostr(c1) + inttostr(c2) + inttostr(c3) +
                inttostr(c4) + inttostr(c5) + inttostr(c6));
              zeronetochar6(g, x);
              trans[ord(PGPchr64[g])] := x;
            End;
End;


// Convert base 8 AnsiStrings to base 6 AnsiStrings and visa versa

Procedure ConvertBase256to64(Const str256: AnsiString; Var str64: AnsiString);
Var
  temp: AnsiString;
  trans: Array [0 .. 255] Of AnsiString;
  i, len6: longint;
  g: integer;
Begin
  initialize8(trans);
  temp := '';
  For i := 1 To Length(str256) Do
    temp := temp + trans[ord(str256[i])];
  While (Length(temp) Mod 6) <> 0 Do
    temp := temp + '0';
  len6 := Length(temp) Div 6;
  str64 := '';
  For i := 1 To len6 Do
  Begin
    zeronetochar6(g, copy(temp, 1, 6));
    str64 := str64 + chr64[g];
    delete(temp, 1, 6);
  End;
End;

Procedure ConvertBase64to256(Const str64: AnsiString; Var str256: AnsiString);
Var
  temp: AnsiString;
  trans: Array [0 .. 255] Of AnsiString;
  i, len8: longint;
  g: AnsiChar;
Begin
  initialize6(trans);
  temp := '';
  For i := 1 To Length(str64) Do
    temp := temp + trans[ord(str64[i])];
  str256 := '';
  len8 := Length(temp) Div 8;
  For i := 1 To len8 Do
  Begin
    zeronetochar8(g, copy(temp, 1, 8));
    str256 := str256 + g;
    delete(temp, 1, 8);
  End;
End;


// Convert base 8 & 6 bit AnsiStrings to base 2 AnsiStrings and visa versa

Procedure ConvertBase256to2(Const str256: AnsiString; Var str2: AnsiString);
Var
  trans: Array [0 .. 255] Of AnsiString;
  i: longint;
Begin
  str2 := '';
  initialize8(trans);
  For i := 1 To Length(str256) Do
    str2 := str2 + trans[ord(str256[i])];
End;

Procedure ConvertBase64to2(Const str64: AnsiString; Var str2: AnsiString);
Var
  trans: Array [0 .. 255] Of AnsiString;
  i: longint;
Begin
  str2 := '';
  initialize6(trans);
  For i := 1 To Length(str64) Do
    str2 := str2 + trans[ord(str64[i])];
End;

Procedure ConvertBase2to256(str2: AnsiString; Var str256: AnsiString);
Var
  i, len8: longint;
  g: AnsiChar;
Begin
  str256 := '';
  While (Length(str2) Mod 8) <> 0 Do
    str2 := '0' + str2;
  len8 := Length(str2) Div 8;
  For i := 1 To len8 Do
  Begin
    zeronetochar8(g, copy(str2, 1, 8));
    str256 := str256 + g;
    delete(str2, 1, 8);
  End;
End;

Procedure ConvertBase2to64(str2: AnsiString; Var str64: AnsiString);
Var
  i, len6: longint;
  g: integer;
Begin
  str64 := '';
  While (Length(str2) Mod 6) <> 0 Do
    str2 := '0' + str2;
  len6 := Length(str2) Div 6;
  For i := 1 To len6 Do
  Begin
    zeronetochar6(g, copy(str2, 1, 6));
    str64 := str64 + chr64[g];
    delete(str2, 1, 6);
  End;
End;


// Convert base 256 AnsiStrings to base 16 (HexaDecimal) AnsiStrings and visa versa

Procedure ConvertBase256StringToHexString(str256: AnsiString;
  Var HexStr: AnsiString);
Var
  i: longint;
  b: byte;
Begin
  HexStr := '';
  For i := 1 To Length(str256) Do
  Begin
    b := ord(str256[i]);
    If (b Shr 4) < 10 Then
      HexStr := HexStr + AnsiChar(48 + (b Shr 4))
    Else
      HexStr := HexStr + AnsiChar(55 + (b Shr 4));
    If (b And 15) < 10 Then
      HexStr := HexStr + AnsiChar(48 + (b And 15))
    Else
      HexStr := HexStr + AnsiChar(55 + (b And 15));
  End;
End;

Procedure ConvertHexStringToBase256String(HexStr: AnsiString;
  Var str256: AnsiString);
Var
  i: longint;
  b, h1, h2: byte;
Begin
  str256 := '';
  For i := 1 To (Length(HexStr) Div 2) Do
  Begin
    h2 := ord(HexStr[2 * i]);
    h1 := ord(HexStr[2 * i - 1]);
    If h1 < 58 Then
      b := ((h1 - 48) Shl 4)
    Else
      b := ((h1 - 55) Shl 4);
    If h2 < 58 Then
      b := (b Or (h2 - 48))
    Else
      b := (b Or (h2 - 55));
    str256 := str256 + AnsiChar(b);
  End;
End;


// Convert base 256 AnsiStrings to base 64 AnsiStrings and visa versa, PGP style

Procedure PGPConvertBase256to64(Var str256, str64: AnsiString);
Var
  temp, x, a: AnsiString;
  i, len6: longint;
  g: integer;
  trans: Array [0 .. 255] Of AnsiString;
Begin
  initialize8(trans);
  temp := '';
  For i := 1 To Length(str256) Do
    temp := temp + trans[ord(str256[i])];
  If (Length(temp) Mod 6) = 0 Then
    a := ''
  Else If (Length(temp) Mod 6) = 4 Then
  Begin
    temp := temp + '00';
    a := '='
  End
  Else
  Begin
    temp := temp + '0000';
    a := '=='
  End;
  str64 := '';
  len6 := Length(temp) Div 6;
  For i := 1 To len6 Do
  Begin
    x := copy(temp, 1, 6);
    zeronetochar6(g, x);
    str64 := str64 + PGPchr64[g];
    delete(temp, 1, 6);
  End;
  str64 := str64 + a;
End;

Procedure PGPConvertBase64to256(str64: AnsiString; Var str256: AnsiString);
Var
  temp, x: AnsiString;
  i, j, len8: longint;
  g: AnsiChar;
  trans: Array [0 .. 255] Of AnsiString;
Begin
  initialize6PGP(trans);
  temp := '';
  str256 := '';
  If str64[Length(str64) - 1] = '=' Then
    j := 2
  Else If str64[Length(str64)] = '=' Then
    j := 1
  Else
    j := 0;
  For i := 1 To (Length(str64) - j) Do
    temp := temp + trans[ord(str64[i])];
  If j <> 0 Then
    delete(temp, Length(temp) - 2 * j + 1, 2 * j);
  len8 := Length(temp) Div 8;
  For i := 1 To len8 Do
  Begin
    x := copy(temp, 1, 8);
    zeronetochar8(g, x);
    str256 := str256 + g;
    delete(temp, 1, 8);
  End;
End;

// Convert base 64 AnsiStrings to base 2 AnsiStrings, PGP style

Procedure PGPConvertBase64to2(str64: AnsiString; Var str2: AnsiString);
Var
  i, j: longint;
  trans: Array [0 .. 255] Of AnsiString;
Begin
  str2 := '';
  initialize6(trans);
  If str64[Length(str64) - 1] = '=' Then
    j := 2
  Else If str64[Length(str64)] = '=' Then
    j := 1
  Else
    j := 0;
  For i := 1 To (Length(str64) - j) Do
    str2 := str2 + trans[ord(str64[i])];
  delete(str2, Length(str2) - 2 * j + 1, 2 * j);
End;


// Convert a base 10 AnsiString to a FGInt

Procedure Base10StringToFGInt(Base10: AnsiString; Var FGInt: TFGInt);
Var
  i, size: longint;
  j: int64;
  S: AnsiString;
  Sign: TSign;

  Procedure GIntDivByIntBis1(Var GInt: TFGInt; by: int64; Var modres: int64);
  Var
    i, size: longint;
    rest: int64;
  Begin
    size := GInt.Number[0];
    modres := 0;
    For i := size Downto 1 Do
    Begin
      modres := modres * 1000000000;
      rest := modres + GInt.Number[i];
      GInt.Number[i] := rest Div by;
      modres := rest Mod by;
    End;
    While (GInt.Number[size] = 0) And (size > 1) Do
      size := size - 1;
    If size <> GInt.Number[0] Then
    Begin
      SetLength(GInt.Number, size + 1);
      GInt.Number[0] := size;
    End;
  End;

Begin
  While (Not(Base10[1] In ['-', '0' .. '9'])) And (Length(Base10) > 1) Do
    delete(Base10, 1, 1);
  If copy(Base10, 1, 1) = '-' Then
  Begin
    Sign := negative;
    delete(Base10, 1, 1);
  End
  Else
    Sign := positive;
  While (Length(Base10) > 1) And (copy(Base10, 1, 1) = '0') Do
    delete(Base10, 1, 1);
  size := Length(Base10) Div 9;
  If (Length(Base10) Mod 9) <> 0 Then
    size := size + 1;
  SetLength(FGInt.Number, size + 1);
  FGInt.Number[0] := size;
  For i := 1 To size - 1 Do
  Begin
    FGInt.Number[i] := StrToInt(String(RightStr(Base10, 9)));
    // FGInt.Number[i] := StrToInt((copy(String(Base10), length(String(Base10)) - 8, 9)));
    delete(Base10, Length(Base10) - 8, 9);
  End;
  FGInt.Number[size] := StrToInt(String(Base10));

  S := '';
  While (FGInt.Number[0] <> 1) Or (FGInt.Number[1] <> 0) Do
  Begin
    GIntDivByIntBis1(FGInt, 2, j);
    S := AnsiString(inttostr(j)) + S;
  End;
  S := '0' + S;
  FGIntDestroy(FGInt);
  Base2StringToFGInt(S, FGInt);
  FGInt.Sign := Sign;
End;


// Convert a FGInt to a base 10 AnsiString

Procedure FGIntToBase10String(Const FGInt: TFGInt; Var Base10: AnsiString);
Var
  S: AnsiString;
  j: int64;
  temp: TFGInt;
Begin
  FGIntCopy(FGInt, temp);
  Base10 := '';
  While (temp.Number[0] > 1) Or (temp.Number[1] > 0) Do
  Begin
    FGIntDivByIntBis(temp, 1000000000, j);
    S := AnsiString(inttostr(j));
    While Length(S) < 9 Do
      S := '0' + S;
    Base10 := S + Base10;
  End;
  Base10 := '0' + Base10;
  While (Length(Base10) > 1) And (Base10[1] = '0') Do
    delete(Base10, 1, 1);
  If FGInt.Sign = negative Then
    Base10 := '-' + Base10;
End;



// Destroy a FGInt to free memory

Procedure FGIntDestroy(Var FGInt: TFGInt);
Begin
  FGInt.Number := Nil;
End;


// Compare 2 FGInts in absolute value, returns
// Lt if FGInt1 > FGInt2, St if FGInt1 < FGInt2, Eq if FGInt1 = FGInt2,
// Er otherwise

Function FGIntCompareAbs(Const FGInt1, FGInt2: TFGInt): TCompare;
Var
  size1, size2, i: longint;
Begin
  FGIntCompareAbs := Er;
  size1 := FGInt1.Number[0];
  size2 := FGInt2.Number[0];
  If size1 > size2 Then
    FGIntCompareAbs := Lt
  Else If size1 < size2 Then
    FGIntCompareAbs := St
  Else
  Begin
    i := size2;
    While (FGInt1.Number[i] = FGInt2.Number[i]) And (i > 1) Do
      i := i - 1;
    If FGInt1.Number[i] = FGInt2.Number[i] Then
      FGIntCompareAbs := Eq
    Else If FGInt1.Number[i] < FGInt2.Number[i] Then
      FGIntCompareAbs := St
    Else If FGInt1.Number[i] > FGInt2.Number[i] Then
      FGIntCompareAbs := Lt;
  End;
End;


// Add 2 FGInts, FGInt1 + FGInt2 = Sum

Procedure FGIntAdd(Const FGInt1, FGInt2: TFGInt; Var Sum: TFGInt);
Var
  i, size1, size2, size: longint;
  rest: integer;
  Trest: int64;
Begin
  size1 := FGInt1.Number[0];
  size2 := FGInt2.Number[0];
  If size1 < size2 Then
    FGIntAdd(FGInt2, FGInt1, Sum)
  Else
  Begin
    If FGInt1.Sign = FGInt2.Sign Then
    Begin
      Sum.Sign := FGInt1.Sign;
      SetLength(Sum.Number, size1 + 2);
      rest := 0;
      For i := 1 To size2 Do
      Begin
        Trest := FGInt1.Number[i] + FGInt2.Number[i] + rest;
        Sum.Number[i] := Trest And 2147483647;
        rest := Trest Shr 31;
      End;
      For i := (size2 + 1) To size1 Do
      Begin
        Trest := FGInt1.Number[i] + rest;
        Sum.Number[i] := Trest And 2147483647;
        rest := Trest Shr 31;
      End;
      size := size1 + 1;
      Sum.Number[0] := size;
      Sum.Number[size] := rest;
      While (Sum.Number[size] = 0) And (size > 1) Do
        size := size - 1;
      If Sum.Number[0] > size Then
        SetLength(Sum.Number, size + 1);
      Sum.Number[0] := size;
    End
    Else
    Begin
      If FGIntCompareAbs(FGInt2, FGInt1) = Lt Then
        FGIntAdd(FGInt2, FGInt1, Sum)
      Else
      Begin
        SetLength(Sum.Number, size1 + 1);
        rest := 0;
        For i := 1 To size2 Do
        Begin
          Trest := 2147483648 + FGInt1.Number[i] - FGInt2.Number[i] + rest;
          Sum.Number[i] := Trest And 2147483647;
          If (Trest > 2147483647) Then
            rest := 0
          Else
            rest := -1;
        End;
        For i := (size2 + 1) To size1 Do
        Begin
          Trest := 2147483648 + FGInt1.Number[i] + rest;
          Sum.Number[i] := Trest And 2147483647;
          If (Trest > 2147483647) Then
            rest := 0
          Else
            rest := -1;
        End;
        size := size1;
        While (Sum.Number[size] = 0) And (size > 1) Do
          size := size - 1;
        If size < size1 Then
        Begin
          SetLength(Sum.Number, size + 1);
        End;
        Sum.Number[0] := size;
        Sum.Sign := FGInt1.Sign;
      End;
    End;
  End;
End;

Procedure FGIntChangeSign(Var FGInt: TFGInt);
Begin
  If FGInt.Sign = negative Then
    FGInt.Sign := positive
  Else
    FGInt.Sign := negative;
End;


// Substract 2 FGInts, FGInt1 - FGInt2 = dif

Procedure FGIntSub(Var FGInt1, FGInt2, dif: TFGInt);
Begin
  FGIntChangeSign(FGInt2);
  FGIntAdd(FGInt1, FGInt2, dif);
  FGIntChangeSign(FGInt2);
End;


// multiply a FGInt by an integer, FGInt * by = res, by < 1000000000

Procedure FGIntMulByInt(Const FGInt: TFGInt; Var res: TFGInt; by: int64);
Var
  i, size: longint;
  Trest, rest: int64;
Begin
  size := FGInt.Number[0];
  SetLength(res.Number, size + 2);
  rest := 0;
  For i := 1 To size Do
  Begin
    Trest := FGInt.Number[i] * by + rest;
    res.Number[i] := Trest And 2147483647;
    rest := Trest Shr 31;
  End;
  If rest <> 0 Then
  Begin
    size := size + 1;
    res.Number[size] := rest;
  End
  Else
    SetLength(res.Number, size + 1);
  res.Number[0] := size;
  res.Sign := FGInt.Sign;
End;


// multiply a FGInt by an integer, FGInt * by = res, by < 1000000000

Procedure FGIntMulByIntbis(Var FGInt: TFGInt; by: int64);
Var
  i, size: longint;
  Trest, rest: int64;
Begin
  size := FGInt.Number[0];
  SetLength(FGInt.Number, size + 2);
  rest := 0;
  For i := 1 To size Do
  Begin
    Trest := FGInt.Number[i] * by + rest;
    FGInt.Number[i] := Trest And 2147483647;
    rest := Trest Shr 31;
  End;
  If rest <> 0 Then
  Begin
    size := size + 1;
    FGInt.Number[size] := rest;
  End
  Else
    SetLength(FGInt.Number, size + 1);
  FGInt.Number[0] := size;
End;


// divide a FGInt by an integer, FGInt = res * by + modres

Procedure FGIntDivByInt(Const FGInt: TFGInt; Var res: TFGInt; by: int64;
  Var modres: int64);
Var
  i, size: longint;
  rest: int64;
Begin
  size := FGInt.Number[0];
  SetLength(res.Number, size + 1);
  modres := 0;
  For i := size Downto 1 Do
  Begin
    modres := modres Shl 31;
    rest := modres Or FGInt.Number[i];
    res.Number[i] := rest Div by;
    modres := rest Mod by;
  End;
  While (res.Number[size] = 0) And (size > 1) Do
    size := size - 1;
  SetLength(res.Number, size + 1);
  res.Number[0] := size;
  res.Sign := FGInt.Sign;
End;


// divide a FGInt by an integer, FGInt = FGInt * by + modres

Procedure FGIntDivByIntBis(Var FGInt: TFGInt; by: int64; Var modres: int64);
Var
  i, size: longint;
  rest: int64;
Begin
  size := FGInt.Number[0];
  modres := 0;
  For i := size Downto 1 Do
  Begin
    modres := modres Shl 31;
    rest := modres Or FGInt.Number[i];
    FGInt.Number[i] := rest Div by;
    modres := rest Mod by;
  End;
  While (FGInt.Number[size] = 0) And (size > 1) Do
    size := size - 1;
  If size <> FGInt.Number[0] Then
  Begin
    SetLength(FGInt.Number, size + 1);
    FGInt.Number[0] := size;
  End;
End;


// Reduce a FGInt modulo by (=an integer), FGInt mod by = modres

Procedure FGIntModByInt(Const FGInt: TFGInt; by: int64; Var modres: int64);
Var
  i, size: longint;
  rest: int64;
Begin
  size := FGInt.Number[0];
  modres := 0;
  For i := size Downto 1 Do
  Begin
    modres := modres Shl 31;
    rest := modres + FGInt.Number[i];
    modres := rest Mod by;
  End;
End;


// Returns the FGInt in absolute value

Procedure FGIntAbs(Var FGInt: TFGInt);
Begin
  FGInt.Sign := positive;
End;


// Copy a FGInt1 into FGInt2

Procedure FGIntCopy(Const FGInt1: TFGInt; Var FGInt2: TFGInt);
Begin
  FGInt2.Sign := FGInt1.Sign;
  FGInt2.Number := Nil;
  FGInt2.Number := copy(FGInt1.Number, 0, FGInt1.Number[0] + 1);
End;


// Shift the FGInt to the left in base 2 notation, ie FGInt = FGInt * 2

Procedure FGIntShiftLeft(Var FGInt: TFGInt);
Var
  L, m: int64;
  i, size: longint;
Begin
  size := FGInt.Number[0];
  L := 0;
  For i := 1 To size Do
  Begin
    m := FGInt.Number[i] Shr 30;
    FGInt.Number[i] := ((FGInt.Number[i] Shl 1) Or L) And 2147483647;
    L := m;
  End;
  If L <> 0 Then
  Begin
    SetLength(FGInt.Number, size + 2);
    FGInt.Number[size + 1] := L;
    FGInt.Number[0] := size + 1;
  End;
End;


// Shift the FGInt to the right in base 2 notation, ie FGInt = FGInt div 2

Procedure FGIntShiftRight(Var FGInt: TFGInt);
Var
  L, m: int64;
  i, size: longint;
Begin
  size := FGInt.Number[0];
  L := 0;
  For i := size Downto 1 Do
  Begin
    m := FGInt.Number[i] And 1;
    FGInt.Number[i] := (FGInt.Number[i] Shr 1) Or L;
    L := m Shl 30;
  End;
  If (FGInt.Number[size] = 0) And (size > 1) Then
  Begin
    SetLength(FGInt.Number, size);
    FGInt.Number[0] := size - 1;
  End;
End;


// FGInt = FGInt / 2147483648

Procedure FGIntShiftRightBy31(Var FGInt: TFGInt);
Var
  size: longint;
Begin
  size := FGInt.Number[0];
  If size > 1 Then
  Begin
    FGInt.Number := copy(FGInt.Number, 1, size);
    FGInt.Number[0] := size - 1;
  End
  Else
    FGInt.Number[1] := 0;
End;


// FGInt1 = FGInt1 + FGInt2, FGInt1 > FGInt2

Procedure FGIntAddBis(Var FGInt1: TFGInt; Const FGInt2: TFGInt);
Var
  i, size1, size2: longint;
  rest: integer;
  Trest: int64;
Begin
  size1 := FGInt1.Number[0];
  size2 := FGInt2.Number[0];
  rest := 0;
  For i := 1 To size2 Do
  Begin
    Trest := FGInt1.Number[i] + FGInt2.Number[i] + rest;
    rest := Trest Shr 31;
    FGInt1.Number[i] := Trest And 2147483647;
  End;
  For i := size2 + 1 To size1 Do
  Begin
    Trest := FGInt1.Number[i] + rest;
    rest := Trest Shr 31;
    FGInt1.Number[i] := Trest And 2147483647;
  End;
  If rest <> 0 Then
  Begin
    SetLength(FGInt1.Number, size1 + 2);
    FGInt1.Number[0] := size1 + 1;
    FGInt1.Number[size1 + 1] := rest;
  End;
End;


// FGInt1 = FGInt1 - FGInt2, use only when 0 < FGInt2 < FGInt1

Procedure FGIntSubBis(Var FGInt1: TFGInt; Const FGInt2: TFGInt);
Var
  i, size1, size2: longint;
  rest: integer;
  Trest: int64;
Begin
  size1 := FGInt1.Number[0];
  size2 := FGInt2.Number[0];
  rest := 0;
  For i := 1 To size2 Do
  Begin
    Trest := 2147483648 + FGInt1.Number[i] - FGInt2.Number[i] + rest;
    If (Trest > 2147483647) Then
      rest := 0
    Else
      rest := -1;
    FGInt1.Number[i] := Trest And 2147483647;
  End;
  For i := size2 + 1 To size1 Do
  Begin
    Trest := 2147483648 + FGInt1.Number[i] + rest;
    If (Trest > 2147483647) Then
      rest := 0
    Else
      rest := -1;
    FGInt1.Number[i] := Trest And 2147483647;
  End;
  i := size1;
  While (FGInt1.Number[i] = 0) And (i > 1) Do
    i := i - 1;
  If i < size1 Then
  Begin
    SetLength(FGInt1.Number, i + 1);
    FGInt1.Number[0] := i;
  End;
End;


// Multiply 2 FGInts, FGInt1 * FGInt2 = Prod

Procedure FGIntMul(Const FGInt1, FGInt2: TFGInt; Var Prod: TFGInt);
Var
  i, j, size, size1, size2: longint;
  rest, Trest: int64;
Begin
  size1 := FGInt1.Number[0];
  size2 := FGInt2.Number[0];
  size := size1 + size2;
  SetLength(Prod.Number, size + 1);
  For i := 1 To size Do
    Prod.Number[i] := 0;

  For i := 1 To size2 Do
  Begin
    rest := 0;
    For j := 1 To size1 Do
    Begin
      Trest := Prod.Number[j + i - 1] + FGInt1.Number[j] * FGInt2.Number
        [i] + rest;
      Prod.Number[j + i - 1] := Trest And 2147483647;
      rest := Trest Shr 31;
    End;
    Prod.Number[i + size1] := rest;
  End;

  Prod.Number[0] := size;
  While (Prod.Number[size] = 0) And (size > 1) Do
    size := size - 1;
  If size < Prod.Number[0] Then
  Begin
    SetLength(Prod.Number, size + 1);
    Prod.Number[0] := size;
  End;
  If FGInt1.Sign = FGInt2.Sign Then
    Prod.Sign := positive
  Else
    Prod.Sign := negative;
End;


// Square a FGInt, FGInt?= Square

Procedure FGIntSquare(Const FGInt: TFGInt; Var Square: TFGInt);
Var
  size, size1, i, j: longint;
  rest, Trest: int64;
Begin
  size1 := FGInt.Number[0];
  size := 2 * size1;
  SetLength(Square.Number, size + 1);
  Square.Number[0] := size;
  For i := 1 To size Do
    Square.Number[i] := 0;
  For i := 1 To size1 Do
  Begin
    Trest := Square.Number[2 * i - 1] + FGInt.Number[i] * FGInt.Number[i];
    Square.Number[2 * i - 1] := Trest And 2147483647;
    rest := Trest Shr 31;
    For j := i + 1 To size1 Do
    Begin
      Trest := Square.Number[i + j - 1] + 2 * FGInt.Number[i] * FGInt.Number
        [j] + rest;
      Square.Number[i + j - 1] := Trest And 2147483647;
      rest := Trest Shr 31;
    End;
    Square.Number[i + size1] := rest;
  End;
  Square.Sign := positive;
  While (Square.Number[size] = 0) And (size > 1) Do
    size := size - 1;
  If size < 2 * size1 Then
  Begin
    SetLength(Square.Number, size + 1);
    Square.Number[0] := size;
  End;
End;


// Convert a FGInt to a binary AnsiString (base 2) & visa versa

Procedure FGIntToBase2String(Const FGInt: TFGInt; Var S: AnsiString);
Var
  i: longint;
  j: integer;
Begin
  S := '';
  For i := 1 To FGInt.Number[0] Do
  Begin
    For j := 0 To 30 Do
      S := AnsiString(inttostr(1 And (FGInt.Number[i] Shr j))) + S;
  End;
  While (Length(S) > 1) And (S[1] = '0') Do
    delete(S, 1, 1);
  If S = '' Then
    S := '0';
End;

Procedure Base2StringToFGInt(S: AnsiString; Var FGInt: TFGInt);
Var
  i, j, size: longint;
Begin
  size := Length(S) Div 31;
  If (Length(S) Mod 31) <> 0 Then
    size := size + 1;
  SetLength(FGInt.Number, size + 1);
  FGInt.Number[0] := size;
  j := 1;
  FGInt.Number[j] := 0;
  i := 0;
  While Length(S) > 0 Do
  Begin
    If S[Length(S)] = '1' Then
      FGInt.Number[j] := FGInt.Number[j] Or (1 Shl i);
    i := i + 1;
    If i = 31 Then
    Begin
      i := 0;
      j := j + 1;
      If j <= size Then
        FGInt.Number[j] := 0;
    End;
    delete(S, Length(S), 1);
  End;
  FGInt.Sign := positive;
End;


// Convert a FGInt to an base 256 AnsiString & visa versa

Procedure FGIntToBase256String(Const FGInt: TFGInt; Var str256: AnsiString);
Var
  temp1: AnsiString;
  i, len8: longint;
  g: AnsiChar;
Begin
  FGIntToBase2String(FGInt, temp1);
  While (Length(temp1) Mod 8) <> 0 Do
    temp1 := '0' + temp1;
  len8 := Length(temp1) Div 8;
  str256 := '';
  For i := 1 To len8 Do
  Begin
    zeronetochar8(g, copy(temp1, 1, 8));
    str256 := str256 + g;
    delete(temp1, 1, 8);
  End;
End;

Procedure Base256StringToFGInt(str256: AnsiString; Var FGInt: TFGInt);
Var
  temp1: AnsiString;
  i: longint;
  trans: Array [0 .. 255] Of AnsiString;
Begin
  temp1 := '';
  initialize8(trans);
  For i := 1 To Length(str256) Do
    temp1 := temp1 + trans[ord(str256[i])];
  While (temp1[1] = '0') And (temp1 <> '0') Do
    delete(temp1, 1, 1);
  Base2StringToFGInt(temp1, FGInt);
End;

// Convert an MPI (Multiple Precision Integer, PGP style) to an FGInt &
// visa versa

Procedure PGPMPIToFGInt(PGPMPI: AnsiString; Var FGInt: TFGInt);
Var
  temp: AnsiString;
Begin
  temp := PGPMPI;
  delete(temp, 1, 2);
  Base256StringToFGInt(temp, FGInt);
End;

Procedure FGIntToPGPMPI(FGInt: TFGInt; Var PGPMPI: AnsiString);
Var
  len, i: word;
  c: AnsiChar;
  b: byte;
Begin
  FGIntToBase256String(FGInt, PGPMPI);
  len := Length(PGPMPI) * 8;
  c := PGPMPI[1];
  For i := 7 Downto 0 Do
    If (ord(c) Shr i) = 0 Then
      len := len - 1
    Else
      Break;
  b := len Mod 256;
  PGPMPI := AnsiChar(b) + PGPMPI;
  b := len Div 256;
  PGPMPI := AnsiChar(b) + PGPMPI;
End;


// Exponentiate a FGInt, FGInt^exp = res

Procedure FGIntExp(Const FGInt, exp: TFGInt; Var res: TFGInt);
Var
  temp2, temp3: TFGInt;
  S: AnsiString;
  i: longint;
Begin
  FGIntToBase2String(exp, S);
  If S[Length(S)] = '0' Then
    Base10StringToFGInt('1', res)
  Else
    FGIntCopy(FGInt, res);
  FGIntCopy(FGInt, temp2);
  If Length(S) > 1 Then
    For i := (Length(S) - 1) Downto 1 Do
    Begin
      FGIntSquare(temp2, temp3);
      FGIntCopy(temp3, temp2);
      If S[i] = '1' Then
      Begin
        FGIntMul(res, temp2, temp3);
        FGIntCopy(temp3, res);
      End;
    End;
End;


// Compute FGInt! = FGInt * (FGInt - 1) * (FGInt - 2) * ... * 3 * 2 * 1

Procedure FGIntFac(Const FGInt: TFGInt; Var res: TFGInt);
Var
  one, temp, temp1: TFGInt;
Begin
  FGIntCopy(FGInt, temp);
  Base10StringToFGInt('1', res);
  Base10StringToFGInt('1', one);

  While Not(FGIntCompareAbs(temp, one) = Eq) Do
  Begin
    FGIntMul(temp, res, temp1);
    FGIntCopy(temp1, res);
    FGIntSubBis(temp, one);
  End;

  FGIntDestroy(one);
  FGIntDestroy(temp);
End;


// FGInt = FGInt * 2147483648

Procedure FGIntShiftLeftBy31(Var FGInt: TFGInt);
Var
  f1, f2: int64;
  i, size: longint;
Begin
  size := FGInt.Number[0];
  SetLength(FGInt.Number, size + 2);
  f1 := 0;
  For i := 1 To (size + 1) Do
  Begin
    f2 := FGInt.Number[i];
    FGInt.Number[i] := f1;
    f1 := f2;
  End;
  FGInt.Number[0] := size + 1;
End;


// Divide 2 FGInts, FGInt1 = FGInt2 * QFGInt + MFGInt, MFGInt is always positive

Procedure FGIntDivMod(Var FGInt1, FGInt2, QFGInt, MFGInt: TFGInt);
Var
  one, zero, temp1, temp2: TFGInt;
  s1, s2: TSign;
  i, j, S, t: longint;
Begin
  s1 := FGInt1.Sign;
  s2 := FGInt2.Sign;
  FGIntAbs(FGInt1);
  FGIntAbs(FGInt2);
  FGIntCopy(FGInt1, MFGInt);
  FGIntCopy(FGInt2, temp1);

  If FGIntCompareAbs(FGInt1, FGInt2) <> St Then
  Begin
    S := FGInt1.Number[0] - FGInt2.Number[0];
    SetLength(QFGInt.Number, S + 2);
    QFGInt.Number[0] := S + 1;
    For t := 1 To S Do
    Begin
      FGIntShiftLeftBy31(temp1);
      QFGInt.Number[t] := 0;
    End;
    j := S + 1;
    QFGInt.Number[j] := 0;
    While FGIntCompareAbs(MFGInt, FGInt2) <> St Do
    Begin
      While FGIntCompareAbs(MFGInt, temp1) <> St Do
      Begin
        If MFGInt.Number[0] > temp1.Number[0] Then
          i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number
            [MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1)
        Else
          i := MFGInt.Number[MFGInt.Number[0]]
            Div (temp1.Number[temp1.Number[0]] + 1);
        If (i <> 0) Then
        Begin
          FGIntCopy(temp1, temp2);
          FGIntMulByIntbis(temp2, i);
          FGIntSubBis(MFGInt, temp2);
          QFGInt.Number[j] := QFGInt.Number[j] + i;
          If FGIntCompareAbs(MFGInt, temp2) <> St Then
          Begin
            QFGInt.Number[j] := QFGInt.Number[j] + i;
            FGIntSubBis(MFGInt, temp2);
          End;
        End
        Else
        Begin
          QFGInt.Number[j] := QFGInt.Number[j] + 1;
          FGIntSubBis(MFGInt, temp1);
        End;
      End;
      If MFGInt.Number[0] <= temp1.Number[0] Then
        If FGIntCompareAbs(temp1, FGInt2) <> Eq Then
        Begin
          FGIntShiftRightBy31(temp1);
          j := j - 1;
        End;
    End;
  End
  Else
    Base10StringToFGInt('0', QFGInt);
  S := QFGInt.Number[0];
  While (S > 1) And (QFGInt.Number[S] = 0) Do
    S := S - 1;
  If S < QFGInt.Number[0] Then
  Begin
    SetLength(QFGInt.Number, S + 1);
    QFGInt.Number[0] := S;
  End;
  QFGInt.Sign := positive;

  FGIntDestroy(temp1);
  Base10StringToFGInt('0', zero);
  Base10StringToFGInt('1', one);
  If s1 = negative Then
  Begin
    If FGIntCompareAbs(MFGInt, zero) <> Eq Then
    Begin
      FGIntAdd(QFGInt, one, temp1);
      FGIntCopy(temp1, QFGInt);
      FGIntDestroy(temp1);
      FGIntSub(FGInt2, MFGInt, temp1);
      FGIntCopy(temp1, MFGInt);
    End;
    If s2 = positive Then
      QFGInt.Sign := negative;
  End
  Else
    QFGInt.Sign := s2;
  FGIntDestroy(one);
  FGIntDestroy(zero);

  FGInt1.Sign := s1;
  FGInt2.Sign := s2;
End;


// Same as above but doesn 't compute MFGInt

Procedure FGIntDiv(Var FGInt1, FGInt2, QFGInt: TFGInt);
Var
  one, zero, temp1, temp2, MFGInt: TFGInt;
  s1, s2: TSign;
  i, j, S, t: longint;
Begin
  s1 := FGInt1.Sign;
  s2 := FGInt2.Sign;
  FGIntAbs(FGInt1);
  FGIntAbs(FGInt2);
  FGIntCopy(FGInt1, MFGInt);
  FGIntCopy(FGInt2, temp1);

  If FGIntCompareAbs(FGInt1, FGInt2) <> St Then
  Begin
    S := FGInt1.Number[0] - FGInt2.Number[0];
    SetLength(QFGInt.Number, S + 2);
    QFGInt.Number[0] := S + 1;
    For t := 1 To S Do
    Begin
      FGIntShiftLeftBy31(temp1);
      QFGInt.Number[t] := 0;
    End;
    j := S + 1;
    QFGInt.Number[j] := 0;
    While FGIntCompareAbs(MFGInt, FGInt2) <> St Do
    Begin
      While FGIntCompareAbs(MFGInt, temp1) <> St Do
      Begin
        If MFGInt.Number[0] > temp1.Number[0] Then
          i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number
            [MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1)
        Else
          i := MFGInt.Number[MFGInt.Number[0]]
            Div (temp1.Number[temp1.Number[0]] + 1);
        If (i <> 0) Then
        Begin
          FGIntCopy(temp1, temp2);
          FGIntMulByIntbis(temp2, i);
          FGIntSubBis(MFGInt, temp2);
          QFGInt.Number[j] := QFGInt.Number[j] + i;
          If FGIntCompareAbs(MFGInt, temp2) <> St Then
          Begin
            QFGInt.Number[j] := QFGInt.Number[j] + i;
            FGIntSubBis(MFGInt, temp2);
          End;
        End
        Else
        Begin
          QFGInt.Number[j] := QFGInt.Number[j] + 1;
          FGIntSubBis(MFGInt, temp1);
        End;
      End;
      If MFGInt.Number[0] <= temp1.Number[0] Then
        If FGIntCompareAbs(temp1, FGInt2) <> Eq Then
        Begin
          FGIntShiftRightBy31(temp1);
          j := j - 1;
        End;
    End;
  End
  Else
    Base10StringToFGInt('0', QFGInt);
  S := QFGInt.Number[0];
  While (S > 1) And (QFGInt.Number[S] = 0) Do
    S := S - 1;
  If S < QFGInt.Number[0] Then
  Begin
    SetLength(QFGInt.Number, S + 1);
    QFGInt.Number[0] := S;
  End;
  QFGInt.Sign := positive;

  FGIntDestroy(temp1);
  Base10StringToFGInt('0', zero);
  Base10StringToFGInt('1', one);
  If s1 = negative Then
  Begin
    If FGIntCompareAbs(MFGInt, zero) <> Eq Then
    Begin
      FGIntAdd(QFGInt, one, temp1);
      FGIntCopy(temp1, QFGInt);
      FGIntDestroy(temp1);
      FGIntSub(FGInt2, MFGInt, temp1);
      FGIntCopy(temp1, MFGInt);
    End;
    If s2 = positive Then
      QFGInt.Sign := negative;
  End
  Else
    QFGInt.Sign := s2;
  FGIntDestroy(one);
  FGIntDestroy(zero);
  FGIntDestroy(MFGInt);

  FGInt1.Sign := s1;
  FGInt2.Sign := s2;
End;


// Same as above but this computes MFGInt in stead of QFGInt
// MFGInt = FGInt1 mod FGInt2

Procedure FGIntMod(Var FGInt1, FGInt2, MFGInt: TFGInt);
Var
  one, zero, temp1, temp2: TFGInt;
  s1, s2: TSign;
  i: int64;
  S, t: longint;
Begin
  s1 := FGInt1.Sign;
  s2 := FGInt2.Sign;
  FGIntAbs(FGInt1);
  FGIntAbs(FGInt2);
  FGIntCopy(FGInt1, MFGInt);
  FGIntCopy(FGInt2, temp1);

  If FGIntCompareAbs(FGInt1, FGInt2) <> St Then
  Begin
    S := FGInt1.Number[0] - FGInt2.Number[0];
    For t := 1 To S Do
      FGIntShiftLeftBy31(temp1);
    While FGIntCompareAbs(MFGInt, FGInt2) <> St Do
    Begin
      While FGIntCompareAbs(MFGInt, temp1) <> St Do
      Begin
        If MFGInt.Number[0] > temp1.Number[0] Then
          i := (2147483648 * MFGInt.Number[MFGInt.Number[0]] + MFGInt.Number
            [MFGInt.Number[0] - 1]) Div (temp1.Number[temp1.Number[0]] + 1)
        Else
          i := MFGInt.Number[MFGInt.Number[0]]
            Div (temp1.Number[temp1.Number[0]] + 1);
        If (i <> 0) Then
        Begin
          FGIntCopy(temp1, temp2);
          FGIntMulByIntbis(temp2, i);
          FGIntSubBis(MFGInt, temp2);
          If FGIntCompareAbs(MFGInt, temp2) <> St Then
            FGIntSubBis(MFGInt, temp2);
        End
        Else
          FGIntSubBis(MFGInt, temp1);
        // If FGIntCompareAbs(MFGInt, temp1) <> St Then FGIntSubBis(MFGInt,temp1);
      End;
      If MFGInt.Number[0] <= temp1.Number[0] Then
        If FGIntCompareAbs(temp1, FGInt2) <> Eq Then
          FGIntShiftRightBy31(temp1);
    End;
  End;

  FGIntDestroy(temp1);
  Base10StringToFGInt('0', zero);
  Base10StringToFGInt('1', one);
  If s1 = negative Then
  Begin
    If FGIntCompareAbs(MFGInt, zero) <> Eq Then
    Begin
      FGIntSub(FGInt2, MFGInt, temp1);
      FGIntCopy(temp1, MFGInt);
    End;
  End;
  FGIntDestroy(one);
  FGIntDestroy(zero);

  FGInt1.Sign := s1;
  FGInt2.Sign := s2;
End;


// Square a FGInt modulo Modb, FGInt^2 mod Modb = FGIntSM

Procedure FGIntSquareMod(Var FGInt, Modb, FGIntSM: TFGInt);
Var
  temp: TFGInt;
Begin
  FGIntSquare(FGInt, temp);
  FGIntMod(temp, Modb, FGIntSM);
  FGIntDestroy(temp);
End;


// Add 2 FGInts modulo base, (FGInt1 + FGInt2) mod base = FGIntres

Procedure FGIntAddMod(Var FGInt1, FGInt2, base, FGIntres: TFGInt);
Var
  temp: TFGInt;
Begin
  FGIntAdd(FGInt1, FGInt2, temp);
  FGIntMod(temp, base, FGIntres);
  FGIntDestroy(temp);
End;


// Multiply 2 FGInts modulo base, (FGInt1 * FGInt2) mod base = FGIntres

Procedure FGIntMulMod(Var FGInt1, FGInt2, base, FGIntres: TFGInt);
Var
  temp: TFGInt;
Begin
  FGIntMul(FGInt1, FGInt2, temp);
  FGIntMod(temp, base, FGIntres);
  FGIntDestroy(temp);
End;


// Exponentiate 2 FGInts modulo base, (FGInt1 ^ FGInt2) mod modb = res

Procedure FGIntModExp(Var FGInt, exp, Modb, res: TFGInt);
Var
  temp2, temp3: TFGInt;
  i: longint;
  S: AnsiString;
Begin
  If (Modb.Number[1] Mod 2) = 1 Then
  Begin
    FGIntMontgomeryModExp(FGInt, exp, Modb, res);
    exit;
  End;
  FGIntToBase2String(exp, S);
  Base10StringToFGInt('1', res);
  FGIntCopy(FGInt, temp2);

  For i := Length(S) Downto 1 Do
  Begin
    If S[i] = '1' Then
    Begin
      FGIntMulMod(res, temp2, Modb, temp3);
      FGIntCopy(temp3, res);
    End;
    FGIntSquareMod(temp2, Modb, temp3);
    FGIntCopy(temp3, temp2);
  End;
  FGIntDestroy(temp2);
End;


// Procedures for Montgomery Exponentiation

Procedure FGIntModBis(Const FGInt: TFGInt; Var FGIntOut: TFGInt; b: longint;
  head: int64);
Var
  i: longint;
Begin
  If b <= FGInt.Number[0] Then
  Begin
    FGIntOut.Number := copy(FGInt.Number, 0, b + 1);
    FGIntOut.Number[b] := FGIntOut.Number[b] And head;
    i := b;
    While (FGIntOut.Number[i] = 0) And (i > 1) Do
      i := i - 1;
    If i < b Then
      SetLength(FGIntOut.Number, i + 1);
    FGIntOut.Number[0] := i;
    FGIntOut.Sign := positive;
  End
  Else
    FGIntCopy(FGInt, FGIntOut);
End;

Procedure FGIntMulModBis(Const FGInt1, FGInt2: TFGInt; Var Prod: TFGInt;
  b: longint; head: int64);
Var
  i, j, size, size1, size2, t: longint;
  rest, Trest: int64;
Begin
  size1 := FGInt1.Number[0];
  size2 := FGInt2.Number[0];
  size := min(b, size1 + size2);
  SetLength(Prod.Number, size + 1);
  For i := 1 To size Do
    Prod.Number[i] := 0;

  For i := 1 To size2 Do
  Begin
    rest := 0;
    t := min(size1, b - i + 1);
    For j := 1 To t Do
    Begin
      Trest := Prod.Number[j + i - 1] + FGInt1.Number[j] * FGInt2.Number
        [i] + rest;
      Prod.Number[j + i - 1] := Trest And 2147483647;
      rest := Trest Shr 31;
    End;
    If (i + size1) <= b Then
      Prod.Number[i + size1] := rest;
  End;

  Prod.Number[0] := size;
  If size = b Then
    Prod.Number[b] := Prod.Number[b] And head;
  While (Prod.Number[size] = 0) And (size > 1) Do
    size := size - 1;
  If size < Prod.Number[0] Then
  Begin
    SetLength(Prod.Number, size + 1);
    Prod.Number[0] := size;
  End;
  If FGInt1.Sign = FGInt2.Sign Then
    Prod.Sign := positive
  Else
    Prod.Sign := negative;
End;

Procedure FGIntMontgomeryMod(Const GInt, base, baseInv: TFGInt;
  Var MGInt: TFGInt; b: longint; head: int64);
Var
  m, temp, temp1: TFGInt;
  r: int64;
Begin
  FGIntModBis(GInt, temp, b, head);
  FGIntMulModBis(temp, baseInv, m, b, head);
  FGIntMul(m, base, temp1);
  FGIntDestroy(temp);
  FGIntAdd(temp1, GInt, temp);
  FGIntDestroy(temp1);
  MGInt.Number := copy(temp.Number, b - 1, temp.Number[0] - b + 2);
  MGInt.Sign := positive;
  MGInt.Number[0] := temp.Number[0] - b + 1;
  FGIntDestroy(temp);
  If (head Shr 30) = 0 Then
    FGIntDivByIntBis(MGInt, head + 1, r)
  Else
    FGIntShiftRightBy31(MGInt);
  If FGIntCompareAbs(MGInt, base) <> St Then
    FGIntSubBis(MGInt, base);
  FGIntDestroy(temp);
  FGIntDestroy(m);
End;

Procedure FGIntMontgomeryModExp(Var FGInt, exp, Modb, res: TFGInt);
Var
  temp2, temp3, baseInv, r: TFGInt;
  i, j, t, b: longint;
  S: AnsiString;
  head: int64;
Begin
  FGIntToBase2String(exp, S);
  t := Modb.Number[0];
  b := t;

  If (Modb.Number[t] Shr 30) = 1 Then
    t := t + 1;
  SetLength(r.Number, t + 1);
  r.Number[0] := t;
  r.Sign := positive;
  For i := 1 To t Do
    r.Number[i] := 0;
  If t = Modb.Number[0] Then
  Begin
    head := 2147483647;
    For j := 29 Downto 0 Do
    Begin
      head := head Shr 1;
      If (Modb.Number[t] Shr j) = 1 Then
      Begin
        r.Number[t] := 1 Shl (j + 1);
        Break;
      End;
    End;
  End
  Else
  Begin
    r.Number[t] := 1;
    head := 2147483647;
  End;

  FGIntModInv(Modb, r, temp2);
  If temp2.Sign = negative Then
    FGIntCopy(temp2, baseInv)
  Else
  Begin
    FGIntCopy(r, baseInv);
    FGIntSubBis(baseInv, temp2);
  End;
  // FGIntBezoutBachet(r, modb, temp2, BaseInv);
  FGIntAbs(baseInv);
  FGIntDestroy(temp2);
  FGIntMod(r, Modb, res);
  FGIntMulMod(FGInt, res, Modb, temp2);
  FGIntDestroy(r);

  For i := Length(S) Downto 1 Do
  Begin
    If S[i] = '1' Then
    Begin
      FGIntMul(res, temp2, temp3);
      FGIntDestroy(res);
      FGIntMontgomeryMod(temp3, Modb, baseInv, res, b, head);
      FGIntDestroy(temp3);
    End;
    FGIntSquare(temp2, temp3);
    FGIntDestroy(temp2);
    FGIntMontgomeryMod(temp3, Modb, baseInv, temp2, b, head);
    FGIntDestroy(temp3);
  End;
  FGIntDestroy(temp2);
  FGIntMontgomeryMod(res, Modb, baseInv, temp3, b, head);
  FGIntCopy(temp3, res);
  FGIntDestroy(temp3);
  FGIntDestroy(baseInv);
End;


// Compute the Greatest Common Divisor of 2 FGInts

Procedure FGIntGCD(Const FGInt1, FGInt2: TFGInt; Var GCD: TFGInt);
Var
  k: TCompare;
  zero, temp1, temp2, temp3: TFGInt;
Begin
  k := FGIntCompareAbs(FGInt1, FGInt2);
  If (k = Eq) Then
    FGIntCopy(FGInt1, GCD)
  Else If (k = St) Then
    FGIntGCD(FGInt2, FGInt1, GCD)
  Else
  Begin
    Base10StringToFGInt('0', zero);
    FGIntCopy(FGInt1, temp1);
    FGIntCopy(FGInt2, temp2);
    While (temp2.Number[0] <> 1) Or (temp2.Number[1] <> 0) Do
    Begin
      FGIntMod(temp1, temp2, temp3);
      FGIntCopy(temp2, temp1);
      FGIntCopy(temp3, temp2);
      FGIntDestroy(temp3);
    End;
    FGIntCopy(temp1, GCD);
    FGIntDestroy(temp2);
    FGIntDestroy(zero);
  End;
End;


// Compute the Least Common Multiple of 2 FGInts

Procedure FGIntLCM(Const FGInt1, FGInt2: TFGInt; Var LCM: TFGInt);
Var
  temp1, temp2: TFGInt;
Begin
  FGIntGCD(FGInt1, FGInt2, temp1);
  FGIntMul(FGInt1, FGInt2, temp2);
  FGIntDiv(temp2, temp1, LCM);
  FGIntDestroy(temp1);
  FGIntDestroy(temp2);
End;


// Trialdivision of a FGInt upto 9999 and stopping when a divisor is found, returning ok=false

Procedure FGIntTrialDiv9999(Const FGInt: TFGInt; Var ok: boolean);
Var
  j: int64;
  i: integer;
Begin
  If ((FGInt.Number[1] Mod 2) = 0) Then
    ok := false
  Else
  Begin
    i := 0;
    ok := true;
    While ok And (i < 1228) Do
    Begin
      i := i + 1;
      FGIntModByInt(FGInt, primes[i], j);
      If j = 0 Then
        ok := false;
    End;
  End;
End;


// A prng

Procedure FGIntRandom1(Var Seed, RandomFGInt: TFGInt);
Var
  temp, base: TFGInt;
Begin
  Base10StringToFGInt('281474976710656', base);
  Base10StringToFGInt('44485709377909', temp);
  FGIntMulMod(Seed, temp, base, RandomFGInt);
  FGIntDestroy(temp);
  FGIntDestroy(base);
End;


// Perform a Rabin Miller Primality Test nrtest times on FGIntp, returns ok=true when FGIntp passes the test

Procedure FGIntRabinMiller(Var FGIntp: TFGInt; nrtest: integer;
  Var ok: boolean);
Var
  j, b, i: int64;
  m, z, temp1, temp2, temp3, zero, one, two, pmin1: TFGInt;
  ok1, ok2: boolean;
Begin
  randomize;
  j := 0;
  Base10StringToFGInt('0', zero);
  Base10StringToFGInt('1', one);
  Base10StringToFGInt('2', two);
  FGIntSub(FGIntp, one, temp1);
  FGIntSub(FGIntp, one, pmin1);

  b := 0;
  While (temp1.Number[1] Mod 2) = 0 Do
  Begin
    b := b + 1;
    FGIntShiftRight(temp1);
  End;
  m := temp1;

  i := 0;
  ok := true;
  randomize;
  While (i < nrtest) And ok Do
  Begin
    i := i + 1;
    Base10StringToFGInt(AnsiString(inttostr(primes[Random(1227) + 1])), temp2);
    FGIntMontgomeryModExp(temp2, m, FGIntp, z);
    FGIntDestroy(temp2);
    ok1 := (FGIntCompareAbs(z, one) = Eq);
    ok2 := (FGIntCompareAbs(z, pmin1) = Eq);
    If Not(ok1 Or ok2) Then
    Begin

      While (ok And (j < b)) Do
      Begin
        If (j > 0) And ok1 Then
          ok := false
        Else
        Begin
          j := j + 1;
          If (j < b) And (Not ok2) Then
          Begin
            FGIntSquareMod(z, FGIntp, temp3);
            FGIntCopy(temp3, z);
            ok1 := (FGIntCompareAbs(z, one) = Eq);
            ok2 := (FGIntCompareAbs(z, pmin1) = Eq);
            If ok2 Then
              j := b;
          End
          Else If (Not ok2) And (j >= b) Then
            ok := false;
        End;
      End;

    End
  End;

  FGIntDestroy(zero);
  FGIntDestroy(one);
  FGIntDestroy(two);
  FGIntDestroy(m);
  FGIntDestroy(z);
  FGIntDestroy(pmin1);
End;


// Compute the coefficients from the Bezout Bachet theorem, FGInt1 * a + FGInt2 * b = GCD(FGInt1, FGInt2)

Procedure FGIntBezoutBachet(Var FGInt1, FGInt2, a, b: TFGInt);
Var
  zero, r1, r2, r3, ta, GCD, temp, temp1, temp2: TFGInt;
Begin
  If FGIntCompareAbs(FGInt1, FGInt2) <> St Then
  Begin
    FGIntCopy(FGInt1, r1);
    FGIntCopy(FGInt2, r2);
    Base10StringToFGInt('0', zero);
    Base10StringToFGInt('1', a);
    Base10StringToFGInt('0', ta);

    Repeat
      FGIntDivMod(r1, r2, temp, r3);
      FGIntDestroy(r1);
      r1 := r2;
      r2 := r3;

      FGIntMul(ta, temp, temp1);
      FGIntSub(a, temp1, temp2);
      FGIntCopy(ta, a);
      FGIntCopy(temp2, ta);
      FGIntDestroy(temp1);

      FGIntDestroy(temp);
    Until FGIntCompareAbs(r3, zero) = Eq;

    FGIntGCD(FGInt1, FGInt2, GCD);
    FGIntMul(a, FGInt1, temp1);
    FGIntSub(GCD, temp1, temp2);
    FGIntDestroy(temp1);
    FGIntDiv(temp2, FGInt2, b);
    FGIntDestroy(temp2);

    FGIntDestroy(ta);
    FGIntDestroy(r1);
    FGIntDestroy(r2);
    FGIntDestroy(GCD);
  End
  Else
    FGIntBezoutBachet(FGInt2, FGInt1, b, a);
End;


// Find the (multiplicative) Modular inverse of a FGInt in a finite ring
// of additive order base

Procedure FGIntModInv(Const FGInt1, base: TFGInt; Var Inverse: TFGInt);
Var
  zero, one, r1, r2, r3, tb, GCD, temp, temp1, temp2: TFGInt;
Begin
  Base10StringToFGInt('1', one);
  FGIntGCD(FGInt1, base, GCD);
  If FGIntCompareAbs(one, GCD) = Eq Then
  Begin
    FGIntCopy(base, r1);
    FGIntCopy(FGInt1, r2);
    Base10StringToFGInt('0', zero);
    Base10StringToFGInt('0', Inverse);
    Base10StringToFGInt('1', tb);

    Repeat
      FGIntDestroy(r3);
      FGIntDivMod(r1, r2, temp, r3);
      FGIntCopy(r2, r1);
      FGIntCopy(r3, r2);

      FGIntMul(tb, temp, temp1);
      FGIntSub(Inverse, temp1, temp2);
      FGIntDestroy(Inverse);
      FGIntDestroy(temp1);
      FGIntCopy(tb, Inverse);
      FGIntCopy(temp2, tb);

      FGIntDestroy(temp);
    Until FGIntCompareAbs(r3, zero) = Eq;

    If Inverse.Sign = negative Then
    Begin
      FGIntAdd(base, Inverse, temp);
      FGIntCopy(temp, Inverse);
    End;

    FGIntDestroy(tb);
    FGIntDestroy(r1);
    FGIntDestroy(r2);
  End;
  FGIntDestroy(GCD);
  FGIntDestroy(one);
End;


// Perform a (combined) primality test on FGIntp consisting of a trialdivision upto 8192,
// if the FGInt passes perform nrRMtests Rabin Miller primality tests, returns ok when a
// FGInt is probably prime

Procedure FGIntPrimetest(Var FGIntp: TFGInt; nrRMtests: integer;
  Var ok: boolean);
Begin
  FGIntTrialDiv9999(FGIntp, ok);
  If ok Then
    FGIntRabinMiller(FGIntp, nrRMtests, ok);
End;


// Computes the Legendre symbol for a any number and
// p a prime, returns 0 if p divides a, 1 if a is a
// quadratic residu mod p, -1 if a is a quadratic
// nonresidu mod p

Procedure FGIntLegendreSymbol(Var a, p: TFGInt; Var L: integer);
Var
  temp1, temp2, temp3, temp4, temp5, zero, one: TFGInt;
  i: int64;
  ok1, ok2: boolean;
Begin
  Base10StringToFGInt('0', zero);
  Base10StringToFGInt('1', one);
  FGIntMod(a, p, temp1);
  If FGIntCompareAbs(zero, temp1) = Eq Then
  Begin
    FGIntDestroy(temp1);
    L := 0;
  End
  Else
  Begin
    FGIntDestroy(temp1);
    FGIntCopy(p, temp1);
    FGIntCopy(a, temp2);
    L := 1;
    While FGIntCompareAbs(temp2, one) <> Eq Do
    Begin
      If (temp2.Number[1] Mod 2) = 0 Then
      Begin
        FGIntSquare(temp1, temp3);
        FGIntSub(temp3, one, temp4);
        FGIntDestroy(temp3);
        FGIntDivByInt(temp4, temp3, 8, i);
        If (temp3.Number[1] Mod 2) = 0 Then
          ok1 := false
        Else
          ok1 := true;
        FGIntDestroy(temp3);
        FGIntDestroy(temp4);
        If ok1 = true Then
          L := L * (-1);
        FGIntDivByIntBis(temp2, 2, i);
      End
      Else
      Begin
        FGIntSub(temp1, one, temp3);
        FGIntSub(temp2, one, temp4);
        FGIntMul(temp3, temp4, temp5);
        FGIntDestroy(temp3);
        FGIntDestroy(temp4);
        FGIntDivByInt(temp5, temp3, 4, i);
        If (temp3.Number[1] Mod 2) = 0 Then
          ok2 := false
        Else
          ok2 := true;
        FGIntDestroy(temp5);
        FGIntDestroy(temp3);
        If ok2 = true Then
          L := L * (-1);
        FGIntMod(temp1, temp2, temp3);
        FGIntCopy(temp2, temp1);
        FGIntCopy(temp3, temp2);
      End;
    End;
    FGIntDestroy(temp1);
    FGIntDestroy(temp2);
  End;
  FGIntDestroy(zero);
  FGIntDestroy(one);
End;


// Compute a square root modulo a prime number
// SquareRoot^2 mod Prime = Square

Procedure FGIntSquareRootModP(Square, Prime: TFGInt; Var SquareRoot: TFGInt);
Var
  one, n, b, S, r, temp, temp1, temp2, temp3: TFGInt;
  a, L, i, j: longint;
Begin
  Base2StringToFGInt('1', one);
  Base2StringToFGInt('2', n);
  a := 0;
  FGIntLegendreSymbol(n, Prime, L);
  While L <> -1 Do
  Begin
    FGIntAddBis(n, one);
    FGIntLegendreSymbol(n, Prime, L);
  End;
  FGIntCopy(Prime, S);
  S.Number[1] := S.Number[1] - 1;
  While (S.Number[1] Mod 2) = 0 Do
  Begin
    FGIntShiftRight(S);
    a := a + 1;
  End;
  FGIntMontgomeryModExp(n, S, Prime, b);
  FGIntAdd(S, one, temp);
  FGIntShiftRight(temp);
  FGIntMontgomeryModExp(Square, temp, Prime, r);
  FGIntDestroy(temp);
  FGIntModInv(Square, Prime, temp1);

  For i := 0 To (a - 2) Do
  Begin
    FGIntSquareMod(r, Prime, temp2);
    FGIntMulMod(temp1, temp2, Prime, temp);
    FGIntDestroy(temp2);
    For j := 1 To (a - i - 2) Do
    Begin
      FGIntSquareMod(temp, Prime, temp2);
      FGIntDestroy(temp);
      FGIntCopy(temp2, temp);
      FGIntDestroy(temp2);
    End;
    If FGIntCompareAbs(temp, one) <> Eq Then
    Begin
      FGIntMulMod(r, b, Prime, temp3);
      FGIntDestroy(r);
      FGIntCopy(temp3, r);
      FGIntDestroy(temp3);
    End;
    FGIntDestroy(temp);
    FGIntDestroy(temp2);
    If i = (a - 2) Then
      Break;
    FGIntSquareMod(b, Prime, temp3);
    FGIntDestroy(b);
    FGIntCopy(temp3, b);
    FGIntDestroy(temp3);
  End;

  FGIntCopy(r, SquareRoot);
  FGIntDestroy(r);
  FGIntDestroy(S);
  FGIntDestroy(b);
  FGIntDestroy(temp1);
  FGIntDestroy(one);
  FGIntDestroy(n);
End;

End.
